In recent years, an information security technique for digital data has gained importance. The information security technique aims at assurance of confidentiality, integrity, and availability, and importance is given to confidentiality due to growing interest in information leakage recently.
In general, as a technique for assuring the confidentiality of digital data, an encryption technique is used. The encryption technique encrypts digital data to be secret (to be referred to as “secret information” hereinafter), and make it difficult to reconstruct secret information when a correction encryption key is not known.
FIG. 10 is a block diagram showing an example of an information security system 3 using the encryption technique.
Initially, at a user terminal 300, a control unit 302 transmits secret information in a storing unit 301 to a storage server apparatus 320 via a communication unit 303.
The storage server apparatus 320 executes an encryption operation for this secret information, and a decryption operation of the encrypted secret information.
In the encryption operation, when a communication unit 323 receives the secret information from the user terminal 300, a control unit 322 acquires an encryption key of the user who transmitted this secret information from a key management unit 324. An encryption/decryption unit 325 encrypts the secret information based on the acquired encryption key, and writes the encrypted secret information in a storing unit 321.
In the decryption operation, when the communication unit 323 receives a secret information read-out request from the user terminal 300, the control unit 322 acquires a decryption key in the storing unit 321 from the key management unit 324. This decryption key is that of the user who possesses the secret information. The encryption/decryption unit 325 decrypts the encrypted secret information based on the acquired decryption key, and returns the decrypted secret information to the user terminal 300 via the communication unit 323.
In such an information security system, a method of deleting a decryption key in the key management unit when original secret information is to be deleted is known. As a merit of this method, even when a copy of data is left in the storage server apparatus, since there is no decryption key, the secret information cannot be decrypted. However, since the security of the encryption technique is based on the computation cost of the current computer performance and deciphering technique, there is a fear that decryption of the secret information from data left in the storage server apparatus could be achieved, owing to progress in computer performance and deciphering techniques.
On the other hand, in addition to the encryption technique, a secret sharing technique as a technique for assuring confidentiality of digital data has received a lot of attention. The secret sharing technique has the following features. That is, secret information is divided to generate a plurality of pieces of share information. Of these pieces of share information, the original secret information can be reconstructed from a set of share information, which satisfies a predetermined set. However, the original secret information does not leak at all from a set of share information, which does not satisfy the predetermined set.
The encryption technique and secret sharing technique are largely different in that the security of the encryption technique is computational theoretic, but that of the secret sharing technique is information theoretic. For example, since the security of the encryption technique is based on a large computation cost required for deciphering, there is a fear of information leakage due to improvement in computer performance. By contrast, since the security of the secret sharing technique is based on the shortage of share information required for reconstruction, there is no fear of information leakage due to improvements in computer performance. In this manner, the security of the two techniques largely differs.
Furthermore, the secret sharing technique can assure availability in addition to confidentiality, and a (k, n) threshold secret sharing scheme proposed by Shamir is representative. The (k, n) threshold secret sharing scheme divides secret information into n pieces of share information, and allows arbitrary k pieces of share information to reconstruct the secret information, but does not allow arbitrary (k−1) pieces of share information to reconstruct the secret information. Note that k and n are respectively natural numbers which satisfy (2≦k≦n).
Since such secret sharing technique assures information theoretic security, a data size of each share information cannot be smaller than that of the original secret information. For this reason, when secret information is divided into n pieces of share information, the total data size of the n pieces of share information becomes n times the original secret information, thus posing a problem.
On the other hand, in recent years, a resource providing service in which a resource provider of a third parity provides a huge resources to users using, for example, cloud computing or the like is growing. As resources, computer resources such as Central Processing Unit (CPU), memories and hard discs (HDD: Hard Disc Drive) are provided as needed. According to such resource providing service, since hard discs of large quantities are available, the aforementioned problem of the data size can be compensated for.
FIG. 11 is a block diagram showing an example of a secret sharing system 4 using a resource providing service. In the secret sharing system 4, a dealer apparatus 400 stores original secret information deposited from the user, and executes sharing processing, a distribution operation, and a reconstruction operation of this secret information. Storage server apparatuses 420, 430, and 440 are those possessed by a resource provider.
For example, in a case of the sharing processing and distribution operation, in the dealer apparatus 400, a share information generating unit 403 executes sharing processing to secret information in a storing unit 401 in accordance with an instruction of a control unit 402. Assume that this sharing processing is based on a (2, 3) threshold secret sharing scheme (k=2, n=3).
After the sharing processing, the dealer apparatus 400 respectively distributes three pieces of share information from a communication unit 404 to the storage server apparatuses 420, 430, and 440 via a network 410.
The storage server apparatuses 420, 430, and 440 respectively receive share information addressed to such apparatuses via communication units 422, 432, and 442, and store the information in storing units 421, 431, and 441.
Further, in a case of the reconstruction operation, the dealer apparatus 400 transmits a share information read-out request from the communication unit 404 to the storage server apparatuses 420, 430, and 440 via the network 410, and receives the returned pieces of share information. Note that the dealer apparatus 400 transmits the share information read-out request to k (k=2) or more storage server apparatuses. The storage server apparatuses as transmission targets of the share information read-out request are arbitrarily selected according to a user operation. Also, an information combining unit 405 combines the received pieces of share information according to an instruction of the control unit 402, thereby reconstructing the original secret information.
In such a secret sharing system, a method of deleting pieces of share information in the k or more storage server apparatuses when original secret information is to be deleted is known.